package exam.dfs;


import java.util.Arrays;
import java.util.Stack;

/**
 * HJ93
 *输入int型数组，询问该数组能否分成两组，使得两组中各元素加起来的和相减等于某一个值
 * @author shenenlu 2021年05月03日 下午21:37:33
 */
public class ArraySplit {

    private boolean canSplit;

    private int[] numberList;

    private int sum;

    private int abs;

    private Stack<Integer> stack;

    public ArraySplit(int[] numberList, int abs) {
        this.numberList = numberList;
        this.sum = Arrays.stream(numberList).sum();
        this.canSplit = false;
        this.abs = abs;
        this.stack = new Stack<>();
    }

    public void dfs(int index, int sumA){
        if( canSplit ){
            return;
        }
        if( Math.abs(sum - 2 * sumA) == abs ){
//            stack.forEach(System.out::print);
            System.out.println(sum+ "|" +sumA + "|" + abs);
            canSplit = true;
        }
        for( int j = index; j < numberList.length; j++){
//            stack.push(numberList[j]);
            dfs(j + 1, sumA + numberList[j] );
//            stack.pop();
            if( canSplit){
                return;
            }
        }
    }


    public static void main(String[] args) {
        ArraySplit arraySplit = new ArraySplit( new int[]{-7, -1,3,6,9}, 2);
        arraySplit.dfs(0, 0);
        System.out.println( arraySplit.canSplit);
    }

}
